package com.zhengwl.study.datastruct;

import java.util.Stack;

/**
 * 
 * @author wlzheng
 * @description 定义：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
 *              （1）若左子树不空，则左子树上所有结点的键值均小于或等于它的根结点的键值；
 *              （2）若右子树不空，则右子树上所有结点的键值均大于或等于它的根结点的键值； 
 *              （3）左、右子树也分别为二叉排序树；
 */
public class BinarySortTree {
	private Node root = null;

	public boolean searchBST(int key) {
		Node current = root;
		while (current != null) {
			if (key == current.getValue())
				return true;
			else if (key < current.getValue())
				current = current.getLeft();
			else
				current = current.getRight();
		}
		return false;
	}

	public void insertBST(int key) {
		Node p = root;
		/** 记录查找结点的前一个结点 */
		Node prev = null;
		/** 一直查找下去，直到到达满足条件的结点位置 */
		while (p != null) {
			prev = p;
			if (key < p.getValue())
				p = p.getLeft();
			else if (key > p.getValue())
				p = p.getRight();
			else
				return;
		}
		/** prve是要安放结点的父节点，根据结点值得大小，放在相应的位置 */
		if (root == null)
			root = new Node(key);
		else if (key < prev.getValue())
			prev.setLeft(new Node(key));
		else
			prev.setRight(new Node(key));

	}

	public void deleteBST(int key) {
		deleteBST(root, key);
	}

	private boolean deleteBST(Node node, int key) {
		if (node == null)
			return false;
		else {
			if (key == node.getValue()) {
				return delete(node);
			} else if (key < node.getValue()) {
				return deleteBST(node.getLeft(), key);
			} else {
				return deleteBST(node.getRight(), key);
			}
		}
	}

	private boolean delete(Node node) {
		Node temp = null;
		/**
		 * 右子树空，只需要重接它的左子树 如果是叶子结点，在这里也把叶子结点删除了
		 */
		if (node.getRight() == null) {
			temp = node;
			node = node.getLeft();
		}
		/** 左子树空， 重接它的右子树 */
		else if (node.getLeft() == null) {
			temp = node;
			node = node.getRight();
		}
		/** 左右子树均不为空 */
		else {
			temp = node;
			Node s = node;
			/** 转向左子树，然后向右走到“尽头” */
			s = s.getLeft();
			while (s.getRight() != null) {
				temp = s;
				s = s.getRight();
			}
			node.setValue(s.getValue());
			if (temp != node) {
				temp.setRight(s.getLeft());
			} else {
				temp.setLeft(s.getLeft());
			}
		}
		return true;
	}

	/**
	 * 中序非递归遍历二叉树 获得有序序列
	 */
	public void nrInOrderTraverse() {
		Stack<Node> stack = new Stack<Node>();
		Node node = root;
		while (node != null || !stack.isEmpty()) {
			while (node != null) {
				stack.push(node);
				node = node.getLeft();
			}
			node = stack.pop();
			System.out.println(node.getValue());
			node = node.getRight();
		}
	}

}
